<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>二分法查找的时间度</title>
</head>
<body>
  <script>
    /**
     * 
     * 给定N个从小到大排好序的整数序列List[]，
     * 以及某待查找整数X，
     * 我们的目标是找到X在List中的下标。
     * 即若有List[i]=X，则返回i；
     * 否则返回-1表示没有找到。
     * 
     * 二分法是先找到序列的中点List[M]，
     * 与X进行比较，若相等则返回中点下标；
     * 否则，若List[M]>X，则在左边的子系列中查找X；
     * 若List[M]<X，则在右边的子系列中查找X。
     * 
     * 二分查找的时间复杂度计算如下：
     * 假设一个数组长度为n,每次查找后数据长度减半，
     * 第一次查找后数据长度为n/2,
     * 第二次查找后数据长度为n/(2的2次方)，
     * 第k次查找后数据长度为n/(2的k次方)，
     * 最坏情况下数数据长度为1时找到该数，
     * 即n/(2的k次方)=1, 解得k=log2(N).
     * 
    */
  </script>
</body>
</html>